//https://www.bilibili.com/video/BV1d54y1f7B3/?spm_id_from=333.337.search-card.all.click&vd_source=d6fe65f095f01f05591e89d810720ccc
// 2024-10-19

import java.util.HashMap;
import java.util.Map;

public class P014_斐波那契数列_动态规划 {

    public static void main(String[] args) {
        System.out.println(fib(20));
    }

    //0,1,1,2,3,5,8.....
    private static int fib(int n) {
        int[] dp = new int[n+1]; // 最大索引到n
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2;i <= n;i++) dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }
}
